
% CHAPTER 5
\chapter{SIMULATION RESULTS}
\label{chp:simulation}
This chapter describes the simulation environment used and gives the simulation results. Various network simulators were studied to simulate the work proposed in this thesis. First part of the work done, simulated in NCTUns and rest of the work simulated on WiMAX Multihop Relay Simulator which is developed by author.  In simulations, end-to-end throughput, queue lengths of superordinate stations and latency of network packets are measured. Chapter consists of three sections;in first section simulation environment will be discussed with their capabilities and simulation models. Topologies that are simulated and simulation results are mentioned in Section 2. Comments on simulation results are given in last section. 
\section{Simulation Environment}
Simulation environment is crucial to evaluate performance of the proposed solution.  There are various network simulators which have implemented commonly used network protocols. Since IEEE 802.16j amendment released at late of 2009, many of the simulators do not have official support. WiMAX Forum gives support to ns2 simulator and there is only IEEE Std 802.16-2009 plug-in available. OPNET has also have WiMAX specialized model but gives support to IEEE 802.16-2004 and IEEE 802.16e-2005.  The only network simulator that gives IEEE 802.16j support is NCTUns 6.0. Currently NCTUns have full support for transparent 802.16j. Non transparent 802.16j module of NCTUns 6.0 is still under development. 
\subsection{NCTUns 6.0}
NCTUns is a powerful simulation tool that runs on Linux. Two key features distinguish it from other well known simulators. One of them is, it uses operating systems TCP/IP stack. Second one is, since it uses OS TCP/IP stack, any real world network applications can be used on NCTUns for testing. NCTUns provides GUI for constructing topologies and traffic models. After simulation completed, with playback option data flow could be seen. 

To enable use of Linux's TCP/IP stack, kernel reentering methodology is used. Pseudo device interfaces named tunnel interface, are used each node in simulation. Every tunnel interface is recognized as a regular network interface by operating system. Figure \ref{fig:chapter5_1} depicts the communication of two hosts in NCTUns simulation. Simulation engine manages only the links between two host and rest of the TCP/IP protocol details are handled with kernel functions. 
\input{chapter5/figure1} 
NCTUns has a modular architecture. Each layer in protocol stack has a corresponding module in NCTUns. Each module may have one precessedor and one successor. Modules communicate with each other with common interfaces. Figure \ref{fig:chapter5_2} shows how two TCP hosts connected via switch on NCTUns. Modules have send() and recv() interfaces for communicating modules on up and down. For calling upper layer module, recv() interface is used  and for calling lower layer module send() interface is used. In Figure \ref{fig:chapter5_2} flow of a packet from Host1 to Host2 is shown. Top layer is inteface module which is visible to application layer and the bottom layer is link layer where the packets forwareded to link layer of the next hop . Here Host1's link layer forwards the packet to Switch's link layer by calling recv() interface and packet propagated up to switch module.  Since the purpose of switch is forwarding the packet right destination, switch module selects the next interface and sends the packet down. Packet is pushed down by calling send() interfaces and pushed up by calling recv() interface in Host2.
\input{chapter5/figure2} 
\subsubsection{Protocol Stacks of IEEE 802.16j Non-transparent Mode Networks in NCTUns}
A device can have more than one interface in NCTUns like Switch. MR-BS has also two interfaces which are IEEE 802.16j interface and Ethernet interface. Protocols stacks of MR-BS, RS and MS are shown in Figure \ref{fig:chapter5_3}. Ethernet interface of MR-BS is for communicating with backbone wired network. Responsibilities of MAC and PHY modules of MR-BS, RS and MS are different so for each device type separate modules are designed. 

MR-BS is connected to backhaul network via Ethernet interface. This connection should have enough bandwidth to carry the whole IEEE 802.16j network traffic. MAC802\_16J\_NT\_PMP\_BS module performs MAC operations like scheduling, connection management. OFDMA\_PMPBS\_MR module performs physical layer operations which use OFDMA technology. CM module simulates the channel model like signal power attenuation, shadowing and multi-path fading effects [17]. MAC802\_16J\_NT\_PMP\_RS module performs scheduling and relaying functionalities. OFDMA\_PMPRS\_MR module encodes and decodes the data transferred to MR-BS and MSs. MAC802\_16J\_NT\_PMP\_MS also performs MAC functionalities including sending receiving message from MR-BS and RS.
\input{chapter5/figure3} 
Main functionalities that are implemented in MAC layer are the initial ranging procedure, the network entry procedure, management message negotiation, network management, connection management and packet scheduling. In initial ranging procedure, MR-BS, RS and MSs synchronize with each other to decode received frames. After successful ranging process, during network entry MR-BS assigns CIDs to RSs and MSs attached to itself. Two management connections and one transport connection are established for each subordinate. Details of RS and BS packet scheduling are shown in Figure \ref{fig:chapter5_4}.
\input{chapter5/figure4}
\subsubsection{Modification for Shortcut Routing}
For proposed shortcut routing mechanism, only MAC802\_16J\_NT\_PMP\_RS module is modified. Since the mechanism is routes the packets according to the IP address, it is not appropriate to do this operation in MAC module. Therefore a new module is attached on top of MAC802\_16J\_NT\_PMP\_RS as in Figure \ref{fig:chapter5_5}. 
\input{chapter5/figure5} 
As stated in the previous chapter, responsibility of 802\_16J\_NT\_CROSS module is to keep IP-CID mappings for shortcut routing. Before modification MAC\_802\_16j\_NT\_PMP\_RS was forwarding data packets received from subordinate station to access link. In opposite direction, RS was checking for the CID of the MAC header, and then forwards the packet to link associated with CID. With modification when a RS receives a data packet, it is sent to 802\_16J\_NT\_CROSS module with CID and UL/DL information. 802\_16J\_NT\_CROSS module modifies the MAC header if shortcut routing possible or directly sends down packet as described in Figure \ref{fig:chapter4_4}.
\subsection{WiMAX Multihop Relay Simulator}
NCTUns is a powerful tool but have some limitations. IEEE 802.16j\_NT module of NCTUns has not released yet. Some of the crucial features of IEEE 802.16j MR networks do not exist. NCTUns 6.0 does not support mobility, multihop connection more than two hops. Automatic frequency selection does not work in PHY module so RSs and BSs interfere with each other. Consequently a simulator which has stated features is needed to verify the proposed model. 
A discrete time event simulator is developed for simulating multihop relaying and burst based network traffic. Simulator is composed of two main parts which are simulation and topology editor. Topology editor is used for creating, viewing and modifying IEEE 802.16j network topologies. Network traffic description is also generated with this tool. Generated topology and traffic description are passed to simulation engine as parameter. During simulation, connection and modification of wireless links can be viewed. Simulation results are printed on standard output. Simulation model is shown in Figure \ref{fig:chapter5_6}.
\input{chapter5/figure6}
Simulation logic of SimulationEngine is given in Figure \ref{fig:chapter5_7}. Each station has interfaces for sending and receiving burst. Stations keep outgoing burst in a queue for each link. All BSs have same total UL bandwidth during simulation. MSs request UL bandwidth before connecting a superordinate. If granted UL bandwidth requests reach to total UL bandwidth, BS does not accept connection requests. Link quality is determined according to distance between source and destination. Adaptive Modulation and Coding Scheme selects MCS level based on link quality. For an allocated bandwidth if higher level of MCS is chosen, then bitrate of link increases. If the one of the relay links of in a path have lower MCS level than burst queue of that link may become congested. To evaluate the performance of proposed algorithms and methods, throughput and congestion are used.
\input{chapter5/figure7} 
\section{Topologies and Simulation Results}
In this section various topologies and traffic scenarios are tested in NCTUns and author's simulator. Topologies are selected for both indicating the difference in algorithms and real world conditions. As stated in previous sections, NCTUns has limitations for IEEE 802.16j Non-transparent mode networks. For this reason complex topologies cannot be tested on NCTUns. For NCTUns the only metric for evaluating the performance is total throughput of the network. In author's simulator, congestion in queues is also used for evaluation. 
\subsection{Scenario 1}
This scenario indicates how shortcut routing affects latency. Simulation was run for a short duration and total throughput evaluated. MS1 and MS2 generate 1Mbps TCP traffic to each other. Without shortcut routing each packet is delivered to MR-BS first which means each packet traverses one hop more. 
\input{chapter5/figure8} 
\subsection{Scenario 2}
In NCTUns 6.0 only supported QoS class is UGS. MR-BS allocates bandwidth for each MS upon request. In this case if all the subscribers communicating with each other with shortcut routing, the only benefit will be decrease in latency. However, for downlink traffic, there is no bandwidth reservation for MSs. This scenario show, with shortcut routing downlink queue of MR-BS will be less congested and network throughput of system will increase. 
\input{chapter5/figure9} 
Shortcut routing performs 30\% better than actual routing mechanism.
\subsection{Scenario 3}
Motivation behind the shortcut routing is to decrease the load of superordinate stations at higher level. Since IEEE 802.16 Non-transparent network forms a tree topology, nodes at higher level becomes heavy loaded. This scenario indicates how decreasing the load of MR-BS increases the throughput.
\input{chapter5/figure10}
\subsection{Scenario 4}
Previous scenarios were designed for observing the effects of shortcut routing. The scenario below has hybrid traffic types where some of them are suitable for shortcut routing and some of are not. Only traffic MS2 to MS1 and MS4 to MS3 will be forwarded from RSs. 
\input{chapter5/figure11} 
7Mbps TCP traffic is generated in overall network and 1Mbps of this traffic is suitable for shortcut routing. The simulation results do not differ so much since the major traffic route is same in both cases. 
\subsection{Scenario 5}
This scenario aims to indicate benefit of proposed metric in path selection. MS4 and MS5 generate TCP traffic destined to each other. MCS and Hop Count metrics directs path selection method to connect directly to base station. At the beginning of the simulation MS4 selects BS1 as access station and MS5 selects BS2. After a while MS4 and MS5 sent and received traffic analysis metric dominates other and MS4 and MS5 choose RS3 as access station. Simulation results without traffic analysis metric and without traffic analysis metric are shown in Figure \ref{fig:chapter5_12} and Figure \ref{fig:chapter5_13} respectively.
\input{chapter5/figure12} 
Throughput=120000 Congestion=1200
\input{chapter5/figure13} 
Throughput=296100 Congestion=3000
\subsection{Scenario 6}
As in Scenario 5, this scenario also depicts the benefits of traffic aware routing algorithm. Compared to previous scenario, there are more MSs deployed and some of them have longer distance to RS in this scenario. Path selection results with traditional metrics are shown in Figure \ref{fig:chapter5_14}. Traffic aware path selection result is shown in Figure \ref{fig:chapter5_15}. MS10's access station is not changed because selecting RS3 as access station may degrade access link quality. Sending traffic over backbone network may be more efficient for MS10. Throughput improvement is lower than previous scenario since MCS level of access links of MS8, MS9 and MS11 is low. 
\input{chapter5/figure14} 
Throughput=480000 Congestion=4800
\input{chapter5/figure15} 
Throughput=628300 Congestion=6300
\subsection{Scenario 7}
Since NCTUns is not mature simulator to test complex topologies, random and complex topologies are tested on author's simulator.  A base topology (Figure \ref{fig:chapter5_16}) is constructed with dense RS deployment to put forward the Multihop Relaying concept. Topology is logically divided into four regions to distribute MSs uniformly. Each region has one MR-BS for serving subordinate stations.
\input{chapter5/figure16} 
A uniform random distribution of 80 MSs is shown in Figure \ref{fig:chapter5_17}. Traffic scenario is semi-random where the probability of destination being in the same region of source node can be declared. By this way, how communication ratio of the nodes in same region affects the proposed path selection method and shortcut routing can be observed. Each MS selects two traffic destinations and has total 300 KHz UL bandwidth. Total UL bandwidths of MR-BSs are 7000 KHz and total DL bandwidth of RSs and MR-BSs are 8000 KHz 
\input{chapter5/figure17} 
Proposed path selection method uses four metrics as stated in previous chapter. Each metrics coefficient is fixed with best values obtained from different simulation runs. Utilization of dedicated bandwidth to each MS is increased in different simulation runs. With low utilization, intermediate RSs will not become congested even if its access link quality is lower than its subordinate's access link. For observing the behavior of proposed methods on local communication, probability of choosing traffic destination in same region is increased in different simulation runs. The results of simulations are show on following graphs. The abbreviations that are used in graphs, is given in Table \ref{tab:chapter5_1}.
\input{chapter5/table1}
\input{chapter5/figure18}
\input{chapter5/figure24}
For the scenario where there is no traffic between subscribers in the same region, our expection is all algorithms should produce similar results. Since there is no shortcut routing opportunity, routing paths are almost same for all schemes. As shown in Figure \ref{fig:chapter5_18} throughput and queue length of RSs are almost same for all algorithms. There is slight improvement for traffic aware routing algorithm. Average latency of a packet is also similar for all algorithms as shown in Figure \ref{fig:chapter5_24}. For the traffic between subscriber from neighbor regions, subscribers may select access station from neighbor RS. Consequently source and destination nodes are connected to same network where shortcut routing possibility exists.
\input{chapter5/figure19} 
\input{chapter5/figure25}
Increasing the probability of choosing traffic destination from the same region, throughput of network improves for the shortcut routing enabled routing schemes. According to Figure \ref{fig:chapter5_19}, throughput and congestion of standard routing algorithm remains same. Performances of algorithms are almost equal when channel utilization is under 50\%. When channel fully utilized, enabling shortcut routing increase throughput 20\% and with using sent \& received data statistics metric throughput improvement reaches 25\%. 
\input{chapter5/figure20}
\input{chapter5/figure26}
Increasing probability of traffic destination being in the same region with source node to 0.5, throughput is 28\% improved with traffic aware routing for higher channel utilization. 
\input{chapter5/figure21}
\input{chapter5/figure27}
\input{chapter5/figure22}
\input{chapter5/figure28}
By inspecting the graphs in Figure \ref{fig:chapter5_20}, Figure \ref{fig:chapter5_21} and Figure \ref{fig:chapter5_22}, increasing the probability of traffic destination being in the same region with source node, throughput is improved for proposed traffic aware routing algorithm and shortcut routing with standard path selection. For standard routing scheme congestion and throughput results almost remain same. Slight differences may result because of traffic scenario changes at each simulation run. Figure \ref{fig:chapter5_21} and Figure \ref{fig:chapter5_22}, throughput and congestion of shortcut routing with standard path selection scheme remains same. Increase in throughput decelerates after bandwidth utilization passes over 50\%. For traffic aware routing, if the probability of traffic destination being in the same region with source node is 1 then there would not be any deceleration in the throughput increase according to Figure \ref{fig:chapter5_22}.
\input{chapter5/figure23}
In Figure \ref{fig:chapter5_23} throughput and congestion with respect to the probability of traffic destination being in the same region of source node is shown. The gap between the compared solutions is getting larger as the probability increases. Consequently proposed traffic aware routing solution performs better for topologies where subscribers in communication with peers in vicinity. For internet usage proposed solution does not provide any benefits since the routing paths almost remain same.
\section{Comments}
Two simulators used to test different topologies and traffic scenarios. Since both simulators have different limitations and assumptions, effects of the proposed solution observed below expectectations. In NCTUns, when RS become bottleneck, it serves only some of subscribers and the rest starves. If we categorize traffic types as inside and outside network, outside network traffic may cause inside network traffic starve. Inside network traffic is the targeted case for throughput improvement in proposed solution. Therefore, throughput improvement could not achieved as expected in such cases.UL and DL scheduler of MR-BS and RSs should be improved to serve each subscriber fairly. 

Comparing the routing algorithms, performances of algorithms diverge according to the utilization of bandwidth dedicated to subscribers and regional communication. If the subscribers do not fill the dedicated bandwidth, then network resources are more than enough to meet the needs. Traffic aware routing performs slightly better than others because of reduction of hop count with shortcut routing. Regional communication is the targeted problem so decreasing the ratio of regional traffic, performance of algorithms converges to each other.

